import UIKit

/*
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。
 示例 1：

 输入：nums = [2,7,11,15], target = 9
 输出：[0,1]
 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
 示例 2：

 输入：nums = [3,2,4], target = 6
 输出：[1,2]
 示例 3：

 输入：nums = [3,3], target = 6
 输出：[0,1]
*/

// 题目只要找两个数的和，非多个的和

/*
 时间O(n3)
 空间O(1)
 */
func twoSum1(nums: [Int], target: Int) -> [Int] {
    var arr = [Int]()
    for i in 0..<nums.count {
        let left = nums[i]
        for j in i+1..<nums.count {
            let right = nums[j]
            if left + right == target, (!arr.contains(i) && !arr.contains(j)) {
                arr.append(i)
                arr.append(j)
                continue
            }
        }
    }
    
    return arr
}

/*
 时间O(n2)
 空间O(1)
 */
func twoSum2(nums: [Int], target: Int) -> [Int] {
    var set = Set<Int>()
    for i in 0..<nums.count {
        let left = nums[i]
        for j in i+1..<nums.count {
            let right = nums[j]
            if left + right == target {
                set.insert(i)
                set.insert(j)
                continue
            }
        }
    }
    
    return Array(set)
}

/*
 时间O(n)
 空间O(n)：其中 NN 是数组中的元素数量。主要为哈希表的开销。
 */
func twoSum3(nums: [Int], target: Int) -> [Int] {
    var values = [Int: Int]()
    for i in 0..<nums.count {
        if let j = values[target - nums[i]] {
            return [i, j]
        }
        values[nums[i]] = i
    }
    return []
}


let arr = twoSum3(nums: [2,7,11,15], target: 9)
print(arr)
